import igraph as ig
import opnc

# 示例图
edges = [(0, 1), (0, 2), (0, 3), (0, 4), (0, 5), (1, 3), (1, 4), (1, 7), (1, 8), (2, 5), (2, 6), (2, 9), (2, 10),
         (3, 7), (4, 8), (6, 9), (6, 10)]

# edges = [(1, 2), (1, 3), (1, 4), (1, 5), (1, 6), (2, 4), (2, 5), (2, 8), (2, 9), (3, 6), (3, 7), (3, 10), (3, 11),
#          (4, 8), (5, 9), (7, 10), (7, 11)]

g = ig.Graph(edges=edges)
opnc.draw_graph(g, layout="fr")

ncs = g.minimum_size_separators()
print(f"所有的节点割集为:{ncs}")

k = g.vertex_connectivity()
print(f"图的节点连通度为{k}")

# 生成原始图的对偶图
dual_g = opnc.generate_dual_graph(g)
opnc.draw_graph_ov(dual_g)

# 生成对偶树
tree = dual_g.spanning_tree()
opnc.draw_graph_ov(tree, layout="tree")
